ARC090 D - People on a Line
https://atcoder.jp/contests/arc090/tasks/arc090_b
解答
code: python
n, m = map(int, input().split())
lrd = list(map(int, input().split())) for _ in range(m)
class WeightedUnionFind():
def __init__(self, n):
self.parent = i for i in range(n)
self.rank = 0 for _ in range(n)
self.diff_weight = 0 for _ in range(n)
def root(self, x):
if self.parentx == x:
return x
root = self.root(self.parentx)
self.diff_weightx += self.diff_weight[self.parentx]
self.parentx = root
return self.parentx
def weight(self, x):
self.root(x)
return self.diff_weightx
def diff(self, x, y):
return self.weight(y) - self.weight(x)
def unite(self, x, y, w):
w += self.weight(x)
w -= self.weight(y)
x = self.root(x)
y = self.root(y)
if x == y:
return
if self.rankx < self.ranky:
self.parentx = y
w = -w
self.diff_weightx = w
elif self.ranky < self.rankx:
self.parenty = x
self.diff_weighty = w
else:
self.parenty = x
self.rankx += 1
self.diff_weighty = w
def same(self, x, y):
return self.root(x) == self.root(y)
wuf = WeightedUnionFind(n+1)
for l, r, d in lrd:
if wuf.same(l, r):
if wuf.diff(l, r) != d:
print('No')
exit()
else:
wuf.unite(l, r, d)
print('Yes')
テーマ
#UnionFind
蟻本 2-4 食物連鎖
メモ
ABC 087 D People on a Line